package search;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-20 14:02
 **/
public class BinarySearch {

    /**
     * 查找左边界模板
     */
    public int searchLeft(int[] nums, int target) {
        int l = 0, r = nums.length-1;
        while(l < r) {
            //关键点：搜索左边界，mid指针永远处于lr的中间偏左的位置
            int mid = (l + r) /2;
            if(nums[l] > target) {
                //关键：r指针挪动到mid位置，此时r符合条件，但因为我们找搜索符合条件的左边界，所以要在lr区间内继续搜索
                r = mid;
            }else {
                //mid不符合条件，l移动到mid+1，避免死循环
                l = mid + 1;
            }
        }
        return l;
    }

    /**
     * 查找右边界模板
     */
    public int searchRight(int[] nums, int target) {
        int l = 0, r = nums.length-1;
        while(l < r) {
            //关键点：搜索左边界，mid指针永远处于lr的中间偏左的位置
            int mid = (l + r) /2;
            if(nums[l] > target) {
                //关键：r指针挪动到mid位置，此时r符合条件，但因为我们找搜索符合条件的左边界，所以要在lr区间内继续搜索
                r = mid;
            }else {
                //mid不符合条件，l移动到mid+1，避免死循环
                l = mid + 1;
            }
        }
        return l;
    }

}
